package com.wdc.queue;

import java.util.*;


/**
 * 二叉树层序遍历
 */
public class E01Leetcode102 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                1,
                new TreeNode(
                        2,
                        new TreeNode(4),
                        new TreeNode(5)
                ),
                new TreeNode(
                        3,
                        new TreeNode(6),
                        new TreeNode(7)
                )

        );

        List<List<Integer>> lists = levelOrder(root);
        System.out.println(lists);

//        //创建一个空队列
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        int c1 = 1; //当前层的节点数
//        while(!queue.isEmpty()){
//            int c2 = 0; //下一层结点数
//            for (int i = 0; i < c1; i++ ) {
//                TreeNode n = queue.poll();
//                System.out.print(n + " ");
//                if (n.left != null){
//                    queue.offer(n.left);
//                    c2++;
//                }
//                if (n.right != null) {
//                    queue.offer(n.right);
//                    c2++;
//                }
//            }
//            c1 = c2;
//            System.out.println();
//        }

    }


    public static List<List<Integer>> levelOrder(TreeNode root) {
        //创建一个空队列
        java.util.Queue<TreeNode> queue = new LinkedList<>();

        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }

        queue.offer(root);
        int c1 = 1; //当前层的节点数
        int c3 = 0; //奇偶
        while(!queue.isEmpty()){
            List<Integer> leve = new ArrayList<>();

            int c2 = 0; //下一层结点数
            for (int i = 0; i < c1; i++ ) {
                TreeNode n = queue.poll();
                leve.add(n.val);
                if (n.left != null){
                    queue.offer(n.left);
                    c2++;
                }
                if (n.right != null) {
                    queue.offer(n.right);
                    c2++;
                }
            }
            c1 = c2;

            result.add(leve);

        }

        return result;
    }

}
